\documentclass[a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\usepackage{hyperref}
\usepackage{url}
\usepackage{ifpdf}
\usepackage{listings}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{color}
\usepackage{mathenv}
\usepackage{graphicx}
\usepackage{caption}
\usepackage{amsthm}
\renewcommand{\familydefault}{\sfdefault}
\title{Les Mathématiques dans les moteurs 3D}
\author{ISMAIL Daline\\COCHU Alexandre\\DAVY Guillaume}
\date{\today}
\hypersetup{colorlinks, linkcolor=black, urlcolor=black,%
pdfauthor={ISMAIL Daline, COCHU Alexandre, DAVY Guillaume},%
pdftitle={{Les Mathématiques dans les moteurs 3D}},%
pdfsubject={{Les Mathématiques dans les moteurs 3D}},%
pdfcreator={LaTeX},%
}
\lstset{language=[light]Caml}
\lstset{tabsize=4}
\begin{document}
	\maketitle
	\pagebreak
	\tableofcontents
	\pagebreak
	
	\section*{Introduction}
	Nous allons dans cet exposé présenter le fonctionnement général d'un moteur 3d. Quels outils mathématiques sont utilisés dans un moteur 3d ?
	Commençons par donner la définition d'un moteur 3d :
	c'est un ensemble de fonctions informatiques permettant l'affichage sur un écran - plan en deux dimensions constitué d'un nombre fini de pixels - d'objets situés dans un espace tridimensionnel virtuel.
	En lui-même, un moteur 3d n'est qu'un outil qui ne peut être utilisé seul : il est appelé par d'autres applications, comme par exemple des jeux.
	En effet, ces logiciels vont donner des ordres au moteur 3D pour qu'il construise, modifie et affiche les éléments qu'ils veulent représenter.
	Il est donc purement générique, c'est à dire que ses fonctions vont par exemple traiter des objets sans en connaître leur représentation 3D exacte.
	Un tel ensemble de fonctions en informatique est appelé bibliothèque de fonctions ; ainsi le moteur 3D est une bibliothèque dont la fonction est de représenter une scène 3d (un ensemble d'objets).
	
	\section{La modélisation et la projection d'une scène 3d}
	Tout d'abord, on doit trouver un moyen efficace de représenter informatiquement cet ensemble d'objets. 

	\subsection{Notion de mesh}
	On commence par s'intéresser aux objets que notre moteur va devoir dessiner.
	Ces objets sont appelés modèles 3D(cf fig\ref{fig1:}).
	\begin{center}
	\includegraphics[scale=0.30]{Pyramide.jpg}
	\captionof{figure}{Pyramide en 3D}
	\label{fig1:}
	\end{center}
	Il faut d'abord noter que la création de ces objets relève du domaine artistique. D'autres logiciels spécifiques permettent leur création(cf fig\ref{fig1:}).
	Notre moteur va se contenter d'afficher le travail créé par un autre logiciel.\\
	Pour cela, le modèle est préalablement sauvegardé dans un fichier. Il sera ensuite lu par notre moteur à l'aide de fonctions de lecture de fichiers qui ne nous intéressent pas ici.\\
	Notons ensuite qu'un modèle 3d peut être représenté par un ensemble de faces, de polygones.
	Ce sont ces polygones que l'on manipulera par la suite, simplifiant ainsi le problème.
	Une surface est constituée d'une infinité de points, donc stocker et gérer une surface point par point est impossible informatiquement parlant.
	Heureusement, on peut montrer, et cela est intuitif que pour définir une surface fermée, son contour suffit.
	Et comme nous sommes dans le cadre de polygones, les sommets du polygone suffisent à condition de les donner dans l'ordre.
	C'est ce que nous faisons en mathématiques lorsque nous nommons des figures dans le plan.\\
	Il va donc falloir pour une face récupérer dans l'ordre toutes les coordonnées de ses points.
	Mais dans un modèle constitué de plusieurs polygones, certains sommets appartiennent à plusieurs faces : il est donc redondant de les donner une fois pour chaque face.
	C'est pourquoi un modèle 3D est en général modélisé par un ensemble de points indicés auquel on adjoint l'ensemble des faces où une face est définie par la donnée dans l'ordre des indices des points qui sont ses sommets.
	Par exemple, pour la pyramide de la fig1 on obtient :
	\begin{center}
		\begin{tabular}{ll}
			1 & (0,0,0) \\
			2 & (2,0,0) \\
			3 & (1,0,2) \\
			4 & (1,2,1) \\
		\end{tabular}
		\captionof{table}{Liste des points}
		\label{tab1:}
		\begin{tabular}{ll}
			1 & 1 2 3 \\
			2 & 1 2 4 \\
			3 & 2 3 4 \\
			4 & 1 3 4 \\
		\end{tabular}
		\captionof{table}{Liste des faces correspondantes}
		\label{tab2:}
	\end{center}
	Evidemment, la donnée des points se fait par leurs coordonnées, ce qui implique que l'on utilise un repère qui est choisi orthonormé par commodité(cf fig\ref{fig2:}).
	\begin{center}
	\includegraphics[scale=0.30]{Repere.jpg}
	\captionof{figure}{Repère 3D dans le logiciel Wings 3D}
	\label{fig2:}
	\end{center}
	Le centre de ce repère est choisi par le créateur du modèle.
	En général il est mis au niveau du centre supposé de l'objet ou bien à un sommet du parallélépipède qui l'entoure.
	Le choix de ce centre n'est pas sans importance, car ensuite l'objet sera tourné, agrandi, autour de celui-ci(cf fig\ref{fig3:}).
	\begin{center}
	\includegraphics[scale=0.15]{Comparaison.jpg}
	\captionof{figure}{Comparaison de deux modèles centrés différemment(avant et après rotation)}
	\label{fig3:}
	\end{center}
	Notons également que les faces sont généralement décomposées en triangles. Ceci est intéressant car un triangle est plan.
	Il faut quand même être sûr que l'on puisse décomposer n'importe quel polygone en triangles.
	Ceci est assez intuitif mais peut très bien être démontré en particulier par l'utilisation d'algorithmes de triangulation comme celui dit de Delaunay.
	Ces algorithmes permettent de décomposer un polygone en triangles.
	Ainsi justifier ces algorithmes mathématiquement permet de montrer que l'on peut bien décomposer n'importe quel polygone en triangles avec en bonus un moyen de le faire.
	Dans les moteurs 3d, ces algorithmes sont rarement utilisés. En effet, les objets sont déjà décomposés sous forme de triangles ou de polygones convexes, dont le traitement est également aisé à faire.
	Ainsi notre modèle 3d est modélisé par un ensemble de points indicés et la liste des faces mais il reste à placer cet objet dans l'espace.
	
	\subsection{Notion de noeud}
	\paragraph{Analyse du problème} ~ \\
	L'ensemble des objets que doit gérer notre moteur 3d s'appelle une scène.
	Chaque objet de la scène est caractérisé par plusieurs types d'informations.
	Si c'est un objet visible, il lui faut le modèle auquel il est associé.
	Et dans tous les cas, on a besoin de sa situation dans l'espace, c'est à dire sa position, sa rotation et sa taille.
	On a sous-entendu qu'il existe des objets invisibles : ces objets sont présents dans la scène mais on ne leur associe pas de modèle.
	Le meilleur exemple est l'objet surnommé caméra. Cet objet sera le point de vue, "l'oeil" de notre scène. Cette caméra pourra bien évidemment être déplacée comme n'importe quel autre objet.
	Les lumières sont elles aussi en général des objets invisibles. Le modeleur pourra s'il le souhaite lui associer un modèle ; sinon, une lumière n'est utilisée que pour le calcul de la luminosité et des ombres.
	\begin{center}
	\includegraphics[scale=0.30]{Rendu.jpg}
	\captionof{figure}{Différence entre les objets visibles et invisibles}
	\label{fig5:}
	\end{center}
	Un dernier point est le fait que parfois deux modèles peuvent être liés dans le contexte de la scène : ainsi, ils peuvent subir les mêmes transformations en tout ou partie.
	Il serait donc intéressant de trouver une structure qui permette d'éviter, si l'on a par exemple 300 objets qui subissent tout le temps les mêmes transformations, d'avoir a faire 300 transformations.
	Pour illustrer ce problème, on peut prendre l'exemple d'un hélicoptère et de ses hélices : hélicoptère + hélices se déplacent ensemble, mais les hélices doivent en plus tourner sur elles-mêmes.
	
	\paragraph{Le modèle} ~ \\
	C'est ce dernier point qui va nous donner l'idée d'un modèle sous forme d'arbre.
	Ainsi, la scène est constituée d'un noeud racine. Et à ce noeud on va pouvoir lier d'autres noeuds que l'on nommera enfants.
	Et toute transformation appliquée au père se répercutera sur les enfants.
	\begin{center}
	\includegraphics[scale=0.30]{Arbre.jpg}
	\captionof{figure}{Exemple de scène structurée sous forme d'arbre}
	\label{fig6:}
	\end{center}
	Ensuite, on va devoir repérer la position des points ; pour cela nous allons travailler dans R3.
	Un point est caractérisé par la donnée d'un uplet, et on ne travaillera qu'avec des repères orthonormés directs.
	A chaque noeud est associé un vecteur position, rotation et mise à l'échelle.
	Le vecteur position donne la position, le vecteur rotation l'angle de rotation sur chacun des axes $x$, $y$, $z$, et le vecteur mise à l'échelle donne l'agrandissement sur chacun des axes.
	Chaque noeud induit un nouveau repère dit local.
	Ainsi, la position des noeuds des enfants ou leur rotation sont données dans le repère du père et non dans le repère global, qui est en fait celui du noeud principal.
	Au noeud est associé, si besoin est, un mesh où toutes les positions sont données dans sa propre base que l'on décide confondue avec la base propre du noeud.
	Ainsi, l'ensemble des points sont donnés dans des coordonnées relatives ; pour l'affichage, il va falloir mettre tout ce petit monde dans le même repère, à savoir celui de la caméra.
	De plus, il faudra passer dans un sens pour remonter aux coordonnées globales, puis dans l'autre pour redescendre aux coordonnées de la caméra.
	En plus de ceci, il faut noter que dans un moteur 3D, les objets sont rarement statiques et il faut donc prévoir des moyens de les translater, pivoter autour d'un point.
	Ceci s'apparente à des changements de bases et fait donc penser à des matrices de passage, qui sont bien ce qui est utilisé dans les moteurs 3d.
	Avant de passer aux matrices, il va nous falloir savoir précisément dans quel espace nous travaillons.

	\subsection{Les espaces affines}
	Nous ne travaillons pas dans $\mathbb{R}^3$ comme espace vectoriel mais $\mathbb{R}^3$ comme espace affine.
	\paragraph{Définitions : } ~ \\
	On pose $\mathbb{K}=$ $\mathbb{R}$ ou $\mathbb{C}$.
	Soit $V$ un espace vectoriel, $E$ un ensemble non vide.
	\subparagraph{Loi scalaire : }
	On appelle une loi scalaire $\varphi$, une application de $E \times E$ dans $V$ qui vérifie les deux propriétés suivantes :
	\begin{align}
		\forall\ ( A , B , C ) \in E^3 ,\ \ \varphi ( A , B ) + \varphi ( B , C ) = \varphi ( A , C )\\
		\forall\ A \in E , \forall\ \vec v \in V , \exists!\ B \in E /\ \ \varphi ( A , B ) = \vec v
	\end{align}
	\subparagraph{Espace affine : }
	Le quadruplet $\varepsilon=(E,\mathbb{K},V,\varphi)$ est appelé espace affine.\\
	$(1)$ et $(2)$ sont appelés les axiomes des espaces affines et $(1)$, la relation de Chasles.\\
	Si $E=V$ et pour $(x,y) \in V^2 , \varphi(x,y) = y - x \in$, $\varepsilon$ est appelé espace affine canonique.\\
	Du coup pour $n \in \mathbb N$, $\mathbb R^n$ est un espace affine canonique.\\
	On pourrait aussi définir le sous espace affine qui rejoindrait la définition du cours à condition de ne se placer que dans le cas d'espace affine canonique.
	\subparagraph{Repère : }
	Soient $B$ une base de $V$ et $O \in E$, alors le couple $R=(O,B)$ est appellé un repère de $\varepsilon$.
	Si en plus $V$ est un espace euclidien et si $B$ est orthonormé, alors $R$ est dit orthonormé aussi.
	\paragraph{Propriétés de base}
	\begin{align}
		\overrightarrow{AB} = \vec 0 \Leftrightarrow A = B\\
		\overrightarrow{BA} = - \overrightarrow{AB}\\
		\overrightarrow{A_1A_n} = \sum_{i = 1}^{n-1} \overrightarrow{A_iA_{i+1}}\\
		\overrightarrow{AB} = \overrightarrow{DC} \Leftrightarrow \overrightarrow{AD} = \overrightarrow{BC}
	\end{align}
	\subsection{Les transformations :}
	Soit $B_n$ la base canonique $\mathbb R^n$.
	\paragraph{Translation :} ~ \\
	Soit $u \in \mathbb R^3$.\\
	On pourrait appeler translation de vecteur $u$ l'application
	\begin{equation}
	\begin{matrix} t_u : \mathbb R^3 & \longrightarrow & { \mathbb R^3 } \\ x & \longmapsto & u + x \end{matrix}
	\end{equation}
	Mais le problème est que cette application n'est pas linéaire. Or nous voulions représenter les transformations par des matrices mais cela nécessite que les transformations soient linéaire. \\
	L'astuce consiste à passer en coordonnées homogènes, c'est à dire travailler dans $\mathbb R^4$ au lieu de $\mathbb R^3$.\\
	Pour passer d'un vecteur de $\mathbb R^3$ à $\mathbb R^4$ il suffit d'utiliser les mêmes composantes en mettant 1 en 4ème.\\
	Soit $u(u_x,u_y,u_z,1) \in \mathbb R^4$.\\
	On peut alors définir la translation de vecteur $u$ comme l'application suivante :\\
	$t_u : \begin{matrix} \mathbb R^4 & \longrightarrow & { \mathbb R^4 } \\ (x,y,z,w) & \longmapsto & (x + u_x w, y + u_y w, z + u_z w, w) \end{matrix}$.\\
	Elle est bien linéaire et à condition de conserver 1 comme 4ème composante elle fait bien une translation.\\
	Soit :
	\begin{equation}
		T_u = \begin{pmatrix} 1 & 0 & 0 & u_x \\ 0 & 1 & 0 & u_y \\ 0 & 0 & 1 & u_z \\ 0 & 0 & 0 & 1 \\ \end{pmatrix}
	\end{equation}
	Alors $M(t_u,B_4) = T_u$.
	
	\paragraph{Rotation :} ~ \\
	Soit $\rho(r,p,y) \in \mathbb R^4$.\\
	On appelle rotation d'axe x et d'angle $r$ l'application :\\
	\begin{equation}
	r_{x,r} : \begin{matrix} \mathbb R^4 & \longrightarrow & { \mathbb R^4 } \\ (x,y,z,w) & \longmapsto & (x, y \cos r - z \sin r, y \sin r + z \cos r, w) \end{matrix}
	\end{equation}
	Travailler dans $\mathbb R^4$ n'est plus indispensable mais comme notre but final est de composer les transformations, on reste dans $\mathbb R^4$.\\
	Il faut donc vérifier que la 4ème composante restera à un après la rotation se qui est le cas, on peut aussi vérifier que l'application est linéaire et bijective.\\
	On peut aussi trouver sa matrice sur $B_4$ :\\
	
	\begin{equation}
	R_{x,r} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & \cos r & - \sin r & 0 \\ 0 & \sin r & \cos r & 0 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix}
	\end{equation}
	
	On pourrait définir de même pour les autres axes et ainsi obtenir $R_{y,p}$ et $R_{z,y}$. Au final la matrice de rotation globale(sur chacun des axes) donnent :\\
	\begin{equation}
	R_\rho = R_{x,r} \times R_{y,p} \times R_{z,y}
	\end{equation}
	Après calcul :
	\begin{equation}
	R_\rho = \begin{pmatrix} \cos p \cos y & - \cos p \sin y & - \sin p & 0 \\ \cos r \sin y - \sin r \sin p \cos y & \cos r \cos y + \sin p \sin y \sin r & -\sin r \cos p & 0 \\ \cos r \sin p \cos y + \sin r \sin y & \sin r \cos y- \cos r \sin p \sin y & \cos r \cos p & 0 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix}
	\end{equation}
	\paragraph{Agrandissement :} ~ \\
	Soit $s(a,b,c,1) \in \mathbb R^4$.\\
	On appelle agrandissement de vecteur $s$ l'application :\\
	\begin{equation}
	a_s : \begin{matrix} \mathbb R^4 & \longrightarrow & { \mathbb R^4 } \\ (x,y,z,w) & \longmapsto & (ax, by, cz, w) \end{matrix}
	\end{equation}
	L'application est linéaire et bijective.\\
	Sa matrice sur la base canonique donne :\\
	\begin{equation}
	A_s = \begin{pmatrix} a & 0 & 0 & 0 \\ 0 & b & 0 & 0 \\ 0 & 0 & c & 0 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix}
	\end{equation}
	\paragraph{Changement de base :} ~ \\
	Un noeud est caractérisé "physiquement" par 3 vecteurs : un de position : $p$, rotation : $\rho$, agrandissement : $s$.\\
	On décide donc de dire qu'un noeud $N$, de position $p$, de rotation $r$ et d'agrandissement $s$ est le triplet $N(p,r,s)$.\\
	On va donc devoir calculé la matrice qui va permettre de passer les points du modèle situé dans le repère local de $N$ au repère global.\\
	Soit $X(x,y,z,w) \in \mathbb R^4$ les coordonnés du modèle dans le repère local et $X'(x',y',z',w') \in \mathbb R^4$ les coordonnées dans le repère globale.
	Il faut d'abord appliqué les rotations et les agrandissements car ils se font par rapport aux centres du repère local puis ensuite la translation.\\
	Au final cela donne :\\
	\begin{equation}
	P_N = T_p \times A_s \times R_s
	\end{equation}
	Après calcul :
	\begin{equation}
	P_N = \begin{pmatrix} a \cos p \cos y & - a \cos p \sin y & - a \sin p & u_x \\ b (\cos r \sin y - \sin r \sin p \cos y) & b(\cos r \cos y + \sin p \sin y \sin r) & - b \sin r \cos p & u_y \\ c (\cos r \sin p \cos y + \sin r \sin y) & c (\sin r \cos y- \cos r \sin p \sin y) & c \cos r \cos p & u_z \\ 0 & 0 & 0 & 1 \\ \end{pmatrix}
	\end{equation}
	Ainsi on a l'égalité suivante : $X'=P_N X$ qui permet de calculer les coordonnées de n'importequel point $X$ de $N$ dans le repère globale.\\
	Chaques points subirat la même transforamtion ainsi $P_N$ ne sera calculé qu'une fois pour chaque noeud.\\
	
	\subsection{Passage de 3 dimensions à 2}
	
	On dispose désormais d'une représentation de notre scène 3d.
	Il nous faut alors décrire les opérations à appliquer sur les triangles composants les modèles 3d afin d'en obtenir des coordonnées utilisables sur notre écran.
	
	\paragraph{Projection perspective}
	Plaçons nous dans l'espace muni d'un repère orthonormé $(O,x,y,z)$.
	On définit un plan $P$ d'équation $z=near$ sur lequel on projettera.
	Soit $M$ de coordonnées $(a,b,c)$ où $(a,b,c) \in R^3$ un point de l'espace.
	Soit $H$ le projeté de $M$ sur l'axe $(Oz)$.
	Alors, on a clairement les relations (par le théorème de thalès) : $\frac{near}{c} = \frac{a_p}{a} = \frac{b_p}{b}$ où $(a_p,b_p) \in R^2$ sont les coordonnées du point $M'$, projeté de $M$ sur le plan $P$. On veut donc pouvoir passer des coordonnées $(a,b,c)$ de tout point $M$ de l'espace aux coordonnées $(a_p,b_p)$ de son projeté sur le plan $P$.
	On a alors $ap=\frac{near \times a}{c}$ et$ bp = \frac{near \times b}{c}$. Il suffit alors de construire une fonction (informatique) qui au triplet $(a,b,c)$ renvoie le couple $(a_p,b_p)$. On pourra si besoin est conserver la profondeur du point (c) en mémoire pour les algorithmes qui vont suivrent (z-buffer notamment).
	
	\paragraph{Application}

	On peut donc désormais projeter un point de l'espace sur un plan en 2d.
	Cependant, de notre point de vue, la caméra ne va pas forcément se trouver au centre du repère global.
	Il nous faut donc effectuer une translation et des rotations à tous les objets de la scène de manière à qu'ils se trouvent tous dans le repère de la caméra.\\
	Or la caméra est un noeud donc elle possède une matrice de passage $P_N$ comme tous les autres noeuds. Sauf que cette matrice permet de passer des coordonnés locales de la caméra aux coordonnés globales. Or se que l'on veut c'est l'inverse : tout avoir dans le repère local de la caméra.\\
	Mais $P_N$ est inversibles comme produit ainsi pour se ramener au repère de la caméra il suffira d'inverser cette matrice avec une des méthodes que nous connaissons bien.\\
	Comme les matrices sont toujours $4\times4$ des algorithmes optimisés existent en se basant sur la méthode de Kramer.\\
	On obtient donc $P_N ^ -1$ et si on note $X''$ les coordonnés dans le repère de la caméra on a $X''=P_N X'$.\\
	Au final tous nos points sont dans le repère de la caméra on peut alors effectuer notre projection.

	
	\section{Dessin de la projection}
	
	Une fois l'opération de projection effectuée, on dispose des coordonnées en 2D de tous les sommets des différentes faces composants les différents objets de la scène.
	Il faut alors, à partir de ces coordonnées, afficher les faces entières à l'écran.
	Cependant, les coordonnées se présentent pour l'instant sous forme de couple de réels, et l'écran d'un ordinateur est composé d'un nombre fini de pixels que l'on peut allumer ou non dans la couleur de notre choix.
	Ainsi, le dessin tel qu'il apparaitra à l'écran ne pourra plus être qu'une approximation des objets que l'on veut représenter.
	
	\subsection{Dessin de segments}

	Le premier exemple de ce que l'on peut vouloir afficher est celui du segment.
	Comment obtenir les coordonnées (entières) des points à afficher alors que l'on ne dispose que des coordonnées (réelles) des extrémités ?
	Commençons par représenter les pixels de l'écran comme des rectangles.
	
	\begin{center}
	\includegraphics[scale=0.30]{segment.jpg}
	\captionof{figure}{Exemple d'utilisation de l'algorithme naïf}
	\label{fig7:}
	\end{center}
	
	Présentons tout d'abord l'algorithme naïf de tracé de segments(cf list\ref{list1:}) : Cette algorithme, très simple, exploite le fait que l'on connait les coordonnées réelles $(x,y)$ de n'importe quel point $M$ du segment $A(x_1,y_1)$ $B(x_2,y_2)$ (en coordonnées entières).
	En effet, on a simplement :
	\begin{equation}
	y=a \times x+b
	\end{equation}
	où
	\begin{align}
	a = \frac{y_2-y_1}{x_2-x_1}\\
	b = y_1-a \times x_1
	\end{align}
	Ainsi, pour $k$ variant de $1$ à $(x_2-x_1)-1$, on peut calculer les coordonnées (entières) du point $M(x_1+k,y_k)$ où $y_k$ est un arrondi du réelle $y=a \times x_k+b$ donnée par la formule précédente.
	Cependant, cette formule ne marche que dans le cas où a élément de $[-1,1]$ et $x_2-x_1>0$; pour $x_1-x_2>0$, on inverse le rôle des points $A$ et $B$ et pour $x_1=x_2$ ou a non élément de $[-1,1]$, on peut considérer que l'on trace un segment dans le repère $(y,x)$ et non pas $(x,y)$.
	Ainsi, on se ramène à chaque fois au premier cas.\\

	Il existe cependant des méthodes plus efficace pour tracer un segment sur un écran d'ordinateur. 
	Un des plus utilisés est sans doute l'algorithme de Bresenham(cf fig\ref{fig8:}).
	Celui-ci optimise simplement l'algorithme précédent afin d'effectuer moins de calculs réels.
	On peut également donner un autre algorithme récursif pour tracer des segments(cf list\ref{list2:}).
	Celui-ci reçoit les coordonnées (réelles) de 2 points (A et B) en argument.
	Puis il calcule les coordonnées du point milieu (M) et affiche le pixel le plus proche.
	Enfin, il s'appelle 2 fois, une fois avec les points A et M, puis une autre avec les points M et B.
	L'algorithme stope lorsque la distance AM devient inférieur à la taille d'un pixel.
	Cet algorithme bien que simple, est extrèmement couteux en temps est n'est en pratique jamais utilisé.
	
	\begin{center}
	\includegraphics[scale=0.30]{Bresenham.png}
	\captionof{figure}{Exemple d'utilisation de l'algorithme de Bresenham}
	\label{fig8:}
	\end{center}
	
	\subsection{Rasterization}

	\paragraph{} On peut ensuite être amener à devoir dessiner des triangles.
	Le processus qui permet de trouver et d'allumer tous les pixels intérieurs à un triangle est appelé rasterization.
	Il existe plusieurs algorithmes, mais nous détaillerons seulement deux d'entre eux.
	Le premier rempli le triangle ligne par ligne : si on veut tracer le triangle $M_1(x_1,y_1)$ $M_2(x_2,y_2)$ $M_3(x_3,y_3)$, pour k variant entre $\min (y_1,y_2,y_3)$ et $\max (y_1,y_2,y_3)$, on cherche l'abscisse des deux points d'intersection de la droite d'équation $y=k$ avec le triangle.
	Ces points d'intersections sont là encore donnés par l'équation réduite des 3 droites qui forment le triangle.
	
	\begin{center}
	\includegraphics[scale=0.30]{scanline.jpg}
	\captionof{figure}{Exemple du scanline}
	\label{fig9:}
	\end{center}

	\paragraph{}Le deuxième algorithme utilise une méthode récursive différente. C'est l'algorithme de remplissage par diffusion.
	On suppose que les côtés du triangle sont déjà dessinés, et que l'on dispose d'une méthode permettant de savoir si un pixel est déjà allumé ou non.
	On part d'un point intérieur du triangle (noté $M(x,y)$ où $x$,$y$ sont entiers).
	Si le point est éteint : on l'allume et on applique l'algorithme aux points de coordonnées $(x-1,y)$, $(x+1,y)$, $(x,y-1)$ et $(x,y+1)$.
	Ainsi, de proche en proche, l'algorithme allume tous les pixels intérieurs au triangle sans aucun calcul.
	Il existe également une variante ou l'on test les 8 pixels adjacents au premiers.
	Cette méthode à l'avantage d'être plus simple et bien plus rapide à coder que la précédente.
	Cependant, cette approche récursive est trop lente.
	
	\subsection{Test de profondeur}
	
	Désormais, on connait des méthodes pour dessiner des segments ou des triangles, polygones primitifs composants tous nos modèles.
	Cependant, un triangle n'est pas forcément visible à l'écran, il peut être caché par d'autres.
	Si l'on dessine tous les triangles de notre scène un à un sans se soucier de leur visibilité respective, les triangles dessinés en dernier vont venir recouvrir ceux déjà à l'écran.
	Une première méthode pour résoudre le problème est donc de trier les triangles en fonction de leur profondeur moyenne (par exemple la profondeur du barycentre).
	Ainsi, si l'on affiche d'abord les triangles les plus lointains, ils seront masqués par ceux plus proches, ce qui correspond à ce que l'on veut obtenir : c'est l'algorithme du peintre.
	Cependant, cette méthode à des limites, notamment dans le cas où deux triangles se coupent selon deux plans sécants, ou dans le cas où trois triangles s'enchevêtrent(cf fig\ref{fig10:}).
	
	\begin{center}
	\includegraphics[scale=0.30]{peintre.jpg}
	\captionof{figure}{Exemple de problème de l'algorithme du peintre}
	\label{fig10:}
	\end{center}
	
	On doit alors recourir à l'algorithme dit du Z-buffer.
	Celui-ci consiste à associer dans une matrice (le Z-buffer ou tampon de profondeur) à chaque pixel de l'écran la profondeur du point correspondant dans l'espace 3d.
	Lorsque l'on veut changer la couleur d'un pixel, on compare tout d'abord la profondeur du point qu'il représente à celle stockée dans le Z-buffer.
	Si le point que l'on essaye de dessiner est devant celui déjà affiché, on peut le remplacer. Cet algorithme impose cependant de connaitre la profondeur de tous les points que l'on dessine.
    De plus, des conflits d'affichage peuvent toujours apparaitre en cas de surfaces coplanaires de couleurs différentes par exemple.
	On a également évincé le problème des surfaces transparentes, qui sont traitées par une technique différente.
	
	\section*{Conclusion}
	Ainsi les moteurs 3D nous ont permis de découvrir quelques applications d'objets mathématiques performants, en particulier dans le cadre de la géométrie avec l’utilisation des espaces affines et projectifs.
	Il faut également bien noter que nous n'avons présenté ici que le noyau de ce qui constitue un vrai moteur 3D. En effet, ceux-ci intègrent les calculs d'ombrages, le texturage des modèles 3d, la gestion de la transparence, et biens d'autres algorithmes de rendu plus avancés.
	Cependant, chacun des ces algorithmes mériterait une présentation dédiée.
	
	\section{Bibliographie}
	
	\paragraph{Site webs :} ~ \\
	\url{http://en.wikipedia.org/wiki/Linear_map}\\
	\url{http://en.wikipedia.org/wiki/3D_modeling}\\
	\url{http://en.wikipedia.org/wiki/Polygon_mesh}\\
	\url{http://en.wikipedia.org/wiki/Subdivision_surfaces}\\
	\url{http://fr.wikipedia.org/wiki/Espace_affine}\\
	\url{http://fr.wikipedia.org/wiki/Application_affine}\\
	\url{http://fr.wikipedia.org/wiki/Espace_projectif}\\
	\url{http://fr.wikipedia.org/wiki/Axiomes_de_plans_projectifs}\\
	\url{http://en.wikipedia.org/wiki/Delaunay_triangulation}\\
	\url{http://fr.wikipedia.org/wiki/Triangulation_de_Delaunay}\\
	\url{http://www.jcoffman.com/Algebra2/ch4_4.htm}\\
	\url{http://www.siggraph.org/education/materials/HyperGraph/scanline/outprims/polygon1.htm}\\
	\url{http://www.massal.net/article/raytrace/page1.html}\\
	\url{http://bobuse.free.fr/Delaunay/}\\
	\url{http://irrlicht.sourceforge.net/}\\
	\url{http://raphaello.univ-fcomte.fr/Ig/}\\
	\url{http://jeux.developpez.com/faq/matquat/}\\
	\paragraph{Sources :} ~ \\
	Irrlicht : \url{http://downloads.sourceforge.net/irrlicht/irrlicht-1.5.zip}\\
	
	\paragraph{Livres :} ~ \\
	Initiation à l'informatique (Programmation,Algorithmique,Architectures) de Henri-Pierre Charles (édition Eyrolles)
	
	\pagebreak
	\section{Annexes:}
	\subsection{Algorithme de tracé de segment naïf :}
	\begin{center}
	\begin{lstlisting}[frame=single][frame=single]
let ligne ((xe1, ye1), (xe2, ye2))=
	let x1=ref xe1 and x2=ref xe2
	and y1=ref ye1 and y2=ref ye2 in
	let dy = float_of_int (!y1 - !y2) in
	let dx = float_of_int (!x1 - !x2) in
	let a = ref ((dy) /. (dx)) in
	plot !x1 !y1;
	plot !x2 !y2;
	if (vabs(!a)>1.) then 
	let s1=ref !x1 and s2=ref !x2 in 
	begin   
		a:=(1./. !a);
		x1:=!y1;
		x2:=!y2;
		y1:=!s1;
		y2:=!s2;
		if (!x1> !x2) then
		begin
			(swap x1 x2);
			(swap y1 y2)
		end;
		let rec aux x =
			let y = !y1 + int(!a *. (float(x - !x1))) in
			plot (y) (x);
			if x <> (!x2) then
				aux (x + 1);
		in
		aux (!x1 + 1)
	end;
	else
	begin
		if (!x1> !x2) then
		begin
			(swap x1 x2);
			(swap y1 y2)
		end;
		let rec aux x =
			let y = !y1 + int(!a *. (float(x - !x1))) in
			plot (x) (y);
			if x <> (!x2) then
				aux (x + 1);
		in
		aux (!x1 + 1)
	end;
;;
	\end{lstlisting}
	\label{list1:}
	\end{center}
	\pagebreak
	\subsection{Algorithme de tracé de segment récursif :}
	\begin{center}
	\begin{lstlisting}[frame=single][frame=single]
let rec rligne ((x1,y1),(x2,y2)) =
   let x = (x1+x2)/2 in
   let y = (y1+y2)/2 in
   plot x y;
   if (x<>x1 & y<>y1) then
		begin
   		rligne ((x1,y1),(x,y));
   		rligne ((x,y),(x2,y2));
		end
;;
	\end{lstlisting}
	\label{list2:}
	\end{center}
	
\end{document}
